As we mentioned before number theory is a branch of mathematics that helps you to study the set of positive whole numbers and one of these sets are the prime number so what it is ? and what is it used for?
Prime numbers are positive integers greater than 1 that have no positive integer divisors other than 1 and themselves.
In simpler words, a prime number is a number that can only be divided evenly by 1 and itself.
There is varies number of ways to find a prime number and some of which are:
Trial division is the simplest method to determine if a number is prime is by dividing it by all the smaller integers greater than 1. If none of the smaller integers divide the number evenly, then the number is prime.
And here is a C++ implementation of the trial division method to check if a given integer “n” is prime:
#include <iostream>
#include <iostream>
using namespace std;
bool isPrime(long long n) {
// Check if n is less than 2
if (n < 2) return false;
// Check if n is divisible by any integer from 2 to sqrt(n)
for (long long i = 2 ; i*i <= n ; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
long long n;
cout << "Enter a positive integer to check if it is prime: " << endl;
cin >> n;
if( n < 1 ) cout << n << " isn't a positive integer." << endl;
else if (isPrime(n)) cout << n << " is prime." << endl;
else cout << n << " is not prime." << endl;
return 0;
}
In this implementation, the isPrime function takes an integer n as an input and returns true if n is prime and false otherwise. The function first checks if n is less than 2, because any number less than 2 is not prime. Then, it checks if n is divisible by any integer from 2 to the square root of n. If n is divisible by any of these integers, it is not prime, and the function returns false. Otherwise, the function returns true.
This is an ancient algorithm for finding all prime numbers up to a given limit. It works by eliminating all multiples of each prime number as they are discovered. To use the Sieve of Eratosthenes, you first create a list of all integers from 2 up to the limit you want to check. Then you mark all multiples of 2, then all multiples of 3, then all multiples of 5, and so on, until you have checked all primes up to the square root of the limit. The remaining unmarked numbers are all prime.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 20;
vector primes ;
vector removed( n , false );
for( int i = 2 ; i <= n ; i++ ){
// if the number 'i' is removed from the list go to the next number
if( removed[i] == true ) continue;
// if this number is not removed that mean it is a prime number
primes.push_back(i);
// we proceed to remove it with its multiples
for( int j = i ; j <= n ; j += i ){
removed[j] = true ;
}
}
cout << "The prime numbers less than " << n << " are : " << endl;
for( auto i : primes )
cout << i << " ";
cout << endl;
return 0;
}
So, this code will do the following process to find all primes up to 20 as such:
• First you create a list of all numbers greater than one and less than or equal to your target and in this case it is 20 as such {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}.
• Then you mark the first element as a prime then remove it with its multiplies and you will end with: Primes {2}, Our list {3,5,7,9,11,13,15,17,19}.
• Repeating the same process again by adding 3 as a prime and removing its multiplies we will end with: Primes {2,3} , Our list {5,7,11,13,17,19}.
• After repeating the process enough times our list will be empty and this is when we stop .
• And in the end we will have a prime list that contains {2,3,5,7,11,13,17,19} as the prime numbers greater than one and less than or equal to our target 20.
Unlike the previous methods Miller-Rabin primality test isn’t deterministic method, meaning we can’t be 100% if the number is prime. However, it is a probabilistic algorithm that is very fast and can determine if a number is likely to be prime with a high degree of confidence.
The algorithm works by testing if the number is a strong pseudoprime to several random bases. A strong pseudoprime is a composite number that behaves like a prime for a certain base. The more bases that are tested, the more confident we can be that the number is prime. The Miller-Rabin primality test is used in many practical applications, including cryptography.
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
// Calculates (a*b) % mod
long long mulmod(long long a, long long b, long long mod) {
long long res = 0;
a %= mod;
while (b > 0) {
if (b % 2 == 1) res = (res + a) % mod;
a = (2 * a) % mod;
b /= 2;
}
return res;
}
// Calculates (a^b) % mod using binary exponentiation
long long power(long long a, long long b, long long mod) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b % 2 == 1) res = mulmod(res, a, mod);
a = mulmod(a, a, mod);
b /= 2;
}
return res;
}
// Miller-Rabin primality test
bool is_prime(long long n, int k) {
if (n < 2) return false;
if (n != 2 && n % 2 == 0) return false;
// Write n-1 as 2^r*d where d is odd
long long d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
r++;
}
// Do k rounds of Miller-Rabin test
for (int i = 0; i < k; i++) {
long long a = 2 + rand() % (n - 2);
long long x = power(a, d, n);
if (x == 1 || x == n-1) continue;
for (int j = 1; j < r; j++) {
x = mulmod(x, x, n);
if (x == 1) return false;
if (x == n-1) break;
}
if (x != n-1) return false;
}
return true;
}
int main() {
int n = 1009 ; // the smallest 4 digit prime
// Test if n is a prime number
if (is_prime(n, 10)) {
cout << n << " is a prime number" << endl;
} else {
cout << n << " is not a prime number" << endl;
}
return 0;
}
In this implementation, is_prime(n, k) tests if n is prime using the Miller-Rabin test with k rounds. The function returns true if n is probably prime and false if it is composite.
Note that the test is probabilistic, which means that it may return a false positive (i.e., claim that a composite number is prime) with a small probability. However, the probability of error decreases as the number of rounds (k) increases. In practice, a value of k=10 is often sufficient for most purposes.
Prime numbers have many applications in the varies number of fields such as:
1. Cryptography where prime numbers are used extensively in modern cryptography to secure online communication such as public-key encryption algorithms like RSA and Diffie-Hellman.
2. Random number generation: Randomness is important in many areas of computer science and cryptography, and prime numbers are often used in the generation of random numbers. For example, one way to generate a random number is to select a large prime number and use it as the starting point for a sequence of pseudorandom numbers.
3. Hash functions: Hash functions are used in computer science to map data of arbitrary size to a fixed-size output. Prime numbers can be used to create robust hash functions that are resistant to collisions, which occur when two different inputs are mapped to the same output.
4. Internet protocols: Prime numbers are used in several internet protocols, including the SSL and TLS protocols that are used to secure web traffic.
5. Error detection and correction: Prime numbers can be used in error detection and correction schemes, which are important for ensuring the integrity of data in computer networks. For example, the cyclic redundancy check (CRC) algorithm uses prime numbers to detect errors in data transmission.
· You can’t memorize all the prime numbers because there are infinite prime numbers in the world and this fact was proven by the ancient Greek mathematician Euclid over 2,000 years ago, and the proof is still used today.
· The distribution of prime numbers is not predictable, and there is no known formula that generates all prime numbers that is why there is a section called how to find them not how to generate them.
· The number 2 is the only even prime number. All other even numbers are divisible by 2.
· The largest known prime number as of September 2021 is 2^(82,589,933) - 1, which has over 24 million digits.